import java.util.ArrayList;
import java.util.List;

import javax.swing.tree.TreeNode;

import jdk.nashorn.api.tree.Tree;

/*
 * @lc app=leetcode.cn id=95 lang=java
 *
 * [95] 不同的二叉搜索树 II
 *
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/
 *
 * algorithms
 * Medium (60.47%)
 * Likes:    244
 * Dislikes: 0
 * Total Accepted:    16K
 * Total Submissions: 26.5K
 * Testcase Example:  '3'
 *
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
 *
 * 示例:
 *
 * 输入: 3
 * 输出:
 * [
 * [1,null,3,2],
 * [3,2,null,1],
 * [3,1,null,null,2],
 * [2,1,3],
 * [1,null,2,null,3]
 * ]
 * 解释:
 * 以上的输出对应以下 5 种不同结构的二叉搜索树：
 *
 * ⁠  1         3     3      2      1
 * ⁠   \       /     /      / \      \
 * ⁠    3     2     1      1   3      2
 * ⁠   /     /       \                 \
 * ⁠  2     1         2                 3
 *
 *
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> list = new ArrayList<>();
        for(int i=1; i <= n; i++) {
            list.addAll(dfs(i, 1, n));
        }
        return list;

    }

    List<TreeNode> dfs(int cur, int left, int right) {
        if(left > right) {
            List<TreeNode> list = new ArrayList<>();
            list.add(null);
            return list;
        }
        List<TreeNode> leftList = new ArrayList<>();
        for(int i = left; i < cur; i++) {
            leftList.addAll(dfs(i, left, cur-1));
        }
        if(leftList.size() == 0) {
            leftList.add(null);
        }
        List<TreeNode> rightList = new ArrayList<>();
        for(int i = cur+1; i <= right; i++) {
            rightList.addAll(dfs(i, cur+1, right));
        }
        if(rightList.size() == 0) {
            rightList.add(null);
        }

        List<TreeNode> list = new ArrayList<>();
        for(TreeNode l : leftList)
            for(TreeNode r : rightList) {
                TreeNode root = new TreeNode(cur);
                root.left = l;
                root.right = r;
                list.add(root);
            }
        return list;

    }
}
// @lc code=end

